package middle;

import java.util.Arrays;
import java.util.List;

public class Solution_139 {

    public boolean wordBreak(String s, List<String> wordDict) {
        char[] chars = s.toCharArray();
        boolean[] flags = new boolean[chars.length];
        for (int i = 0; i < chars.length; i++) {
            boolean flag = false;
            for (String word : wordDict) {
                if (i + 1 < word.length()) {
                    continue;
                }
                boolean wordFlag = true;
                for (int wordIndex = word.length() - 1, sIndex = i; wordIndex >= 0; wordIndex--, sIndex--) {
                    if (word.charAt(wordIndex) != chars[sIndex]) {
                        wordFlag = false;
                        break;
                    }
                }
                if (wordFlag) {
                    if (i >= word.length()) {
                        flag = flags[i - word.length()];
                    } else {
                        flag = true;
                    }
                }
                if (flag) {
                    break;
                }
            }
            flags[i] = flag;
        }
        for (int i = 0; i < flags.length; i++) {
            System.out.println("i = " + i + ";  char = " + chars[i] + ";  flag = " + flags[i]);
        }
        return flags[flags.length - 1];
    }

    public static void main(String[] args) {
        Solution_139 model = new Solution_139();
        System.out.println(model.wordBreak("leetcode", Arrays.asList("leet", "code")));
        System.out.println(model.wordBreak("applepenapple", Arrays.asList("apple", "pen")));
        System.out.println(model.wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat")));
    }
}
